package 二分查找;
/*按照时间复杂度的计算，当mid将数组分为1/2的时候时间复杂度最低，
* 也可以分成三分之一int mid = (right-left)/3+left;，四分之一int mid = (right-left)/4+left;*/

/*当数组长度为奇数时：(right+left)/2或者(right+left+1)/2  无所谓
* 为偶数时，中间值有两个  （right+left）/2 为左中间值，（right+left+1）/2为右中间值
* 总的来说也无所谓，其实都是将其划分成几个部分而已，并不影响最终结果*/
public class 二分查找入门 {
    public static int search(int[] nums, int target) {
      int left = 0, right = nums.length-1;
      while(left<=right){
          int mid = (right-left)/2+left; // 很重要，防止溢出，保持在left与right的中间值
          if(nums[mid]>target){
              right = mid - 1;
          }else if(nums[mid]<target){
              left = mid + 1;
          }else{
              return mid;
          }
      }
        return -1;
    }

    public static void main(String[] args) {
        int [] nums = {-1,0,3,5,9,12};
        int target = 9;

        int z = search(nums,target);
        System.out.println(z);
    }

}
/*朴素二分模板：
* while(left<=right)
* {
*   int mid = left + (right-left)/2;
*   if(.....)
*       left= mid +1;
*   else if(...)
*       right = mid -1 ;
*   else
*       return ...;
* */

/*在二分查找算法中，left 和 right 分别表示当前搜索范围的左右边界。通过计算 (right-left)/2 可以得到当前搜索范围的中间位置的偏移量。然后将这个偏移量加上 left，就可以得到中间位置的索引。

为什么要加上 left 呢？这是因为在每一次迭代中，搜索范围都会被缩小，并且 left 和 right 的值会发生变化。通过加上 left，我们可以将中间位置的相对偏移转换为绝对索引，确保 mid 始终处于正确的位置。

假设初始时 left = 0，right = nums.length-1，那么 (right-left)/2 就等于 (nums.length-1-0)/2 = nums.length/2。如果只是将 nums.length/2 作为中间位置，而不加上 left，那么得到的索引将是相对于整个数组的位置，而不是相对于当前搜索范围的位置。

通过加上 left，我们将中间位置的相对偏移转换为绝对索引，使得 mid 始终表示当前搜索范围内的正确位置。

因此，在代码中使用 mid = (right-left)/2+left 是为了保证 mid 始终表示当前搜索范围内的中间位置的索引。*/